package leetcode.string;

/**
 * @Description: https://leetcode.cn/problems/longest-common-prefix/description/
 * @Author Ammar
 * @Create 2023/7/31 21:00
 */
public class _14_最长公共前缀 {

    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        if (n == 1) return strs[0];
        return longestCP(strs, 0, n - 1);
    }

    public String longestCP(String[] strs, int left, int right) {
        if (left == right) return strs[left];
        int mid = left + (right - left) >> 1;
        String leftLcp = longestCP(strs, left, mid);
        String rightLcp = longestCP(strs, mid + 1, right);
        return cp(leftLcp, rightLcp);
    }

    private String cp(String lcpLeft, String lcpRight) {
        int minLength = Math.min(lcpLeft.length(), lcpRight.length());
        for (int i = 0; i < minLength; i++) {
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
                return lcpLeft.substring(0, i);
            }
        }
        return lcpLeft.substring(0, minLength);
    }
}
